A flash memory is widely used as a data storage device in various types of electronic devices such as a PC (Personal Computer), a data recorder/player, a PDA, and a video camera. The flash memory is easy to write or delete data and has advantages of small size, low weight, high speed, and low power consumption. Because of the above advantages, the flash memory is widely used as a storage medium for storing, for example, image data, audio data, a text file, and/or a program.
In particular, a memory card using a flash memory capable of being removably attached to an electronic device is very widely used. For example, this type of memory card is used such that after video data taken by a video camera is stored into the memory card, the memory card is inserted into a PC and the video data is played back on the PC or such that after music data is downloaded via the Internet or from a storage medium such as a CD, DVD, or MD into a memory card inserted in the PC, and the memory card is inserted in a portable player and the downloaded music data is played black.
As shown in FIG. 1, blocks 110 and pages 120 are defined in the flash memory, wherein deletion of data is performed in units of blocks and reading/writing of data is performed in units of pages. The flash memory includes a plurality of blocks, and each block includes a plurality of pages. Each page includes, for example, a 512-byte data storage area 121 and a 16-byte extension area 122 in which parity data or the like is written. The data sizes of the data storage area and the extension area are set arbitrarily depending on the flash memory. For example, the data size of the data storage area 121 is set to 2048 bytes and the data size of the extension area 122 is set to 64 bytes.
Writing, reading, or deleting of data in the flash memory is performed on a particular data area in the flash memory specified by an address. To specify an address in the flash memory, it is necessary to convert a logical address indicated by addressing information received from an electronic device using the flash memory into a physical address indicating a physical location in the flash memory.
In the flash memory, a logical-physical address conversion table, in which information necessary to convert a logical address to a physical address is described, is stored in a management information area allocated in a particular block in the flash memory.
A specific example of an application of a logical-physical conversion table to a flash memory may be found, for example, in Patent Document 1 (Japanese Unexamined Patent Application Publication No. 2000-47932).
In the flash memory, for example, when data stored in a certain page is read by an electronic device such as a PC and data is updated, the updated data is written at a location different from a page in which the read data was located. This is because the flash memory has an upper limit in terms of the number or times data is written or deleted for the same memory element, and thus it is desirable to use various memory elements instead of using only particular memory elements thereby increasing the overall life of the flash memory.
By performing the address conversion based on the logical-physical address conversion table, it becomes possible to preserve the logical address at the same value even if the physical storage location is changed when data is updated. This allows the electronic device to use the same logical address in reading/writing updated data as the logical address assigned to the data before the data was updated.
It is known in the art to use a FAT (File Allocation Table) as a file management system in a PC or a similar device. The FAT is widely used as management information to indicate file storage locations in various types of storage devices such as a hard disk or a floppy disk. In the FAT, when data is stored in units of clusters, a concatenation from one cluster to another of a set of clusters in which a data file is stored is described in the form of a table. That is, information indicating the cluster-to-cluster concatenation is described in the FAT. The FAT is also used as file management information in the flash memory.
In the flash memory, each block corresponds to one cluster that is defined in the FAT as a unit of a data storage area. That is, when a single data file is stored in a plurality of blocks (corresponding to clusters) of the flash memory, information indicating block-to-block concatenation of those blocks is described in the FAT.
The logical-physical address conversion table and the FAT are stored in particular blocks of the flash memory. When a host device such as a PC or a similar electronic device uses the flash memory, the host device reads the logical-physical address conversion table and the FAT into a RAM (Random Access Memory) disposed in the host device. When data such as music data or image data stored in the flash memory is updated, the logical-physical address conversion table and the FAT stored in the RAM of the host device are also updated under the control of the CPU of the host device. The updated management information is rewritten in the management information area of the flash memory.
In the host device such as a PC on which the memory card using the flash memory is mounted, a process of writing or reading data into or from the memory card is performed as follows. In response to a request from an application program, a file storage location is detected from the FAT. That is, logical addresses of blocks in which the file is stored are acquired from the information indicating the block-to-block concatenation corresponding to cluster-to-cluster concatenation described in the FAT. Furthermore, a logical-to-physical address conversion is performed according to the logical-physical address conversion table, and accessing to physical addresses determined via the logical-to-physical address conversion is performed.
In the flash memory, as described above, writing, reading, and deleting of data are performed in accordance with the FAT and the logical-physical address conversion table. The management information including the FAT and the logical-physical address conversion table is stored in a block of the flash memory.
As described above, when data stored in the flash memory is updated, it is necessary to also update the management information. Referring to a flow chart shown in FIG. 2, a process of updating management information stored in the flash memory is described below. Herein, we assume that management information is stored in a particular block of the flash memory.
First, in step S21, a CPU serving as data write/read/delete means examines the particular block in the flash memory to determine whether the block includes an available page. If an available page is detected in the block, the process proceeds to step S22, but otherwise the process jumps to step S23.
In step S22, the CPU allocates an available page, in the same block as that in which current management information to be updated is stored, for use as a page in which to write updated management information.
On the other hand, in the case in which the process jumps to step S23 because the page in which the management information is stored is the last page of the block, the CPU allocates an available block in the flash memory and further allocates the first page of that block as a new page for use to write updated management information.
In step S24 or S25, the CPU writes updated management information in the new page allocated in step S22 or step S23. In step S26, after completion of writing the updated management information in step S25, all blocks in which the old management information is stored are deleted thereby making those blocks available. Thus, the update process is completed.
In the process described above with reference to the flow chart shown in FIG. 2, the management information stored in blocks of the flash memory are updated as described below with reference to FIG. 3.
Herein we assume that the management information is written into blocks 151 and 152. The writing of the management information in the block 151 is performed starting from page number 0 of the block 151 until reaching page number n. Thereafter, in the block 152, the remaining part of the management information is further written starting from block number 0. As described above, the management information is updated from one block to another.
In the above process, if the updating of the management information stored in the flash memory fails, or if an error occurs in the updating process and new management information is not successfully written, the CPU treats the current management information as newest management information.
In the flash memory, if an error occurs in the process of writing data in a page, an error can affect all data in a block to which the page belongs. This is known as a domino error.
In a domino error, as shown in FIG. 4, if an error occurs at a certain bit in a page of a block, an error also occurs at the same bit in all pages of that block, and thus all data in the block is damaged.
In the process of updating management information stored in the flash memory, as described above with reference to the flow chart shown in FIG. 2, new management information is written in an available page next to a page of a block in which the current management information is written. Therefore, if an error occurs in the updating process, this error causes an error in all management information stored in the same block as the block including the page in which the original error occurred. As a result, the current management information, which must be retained for use as management information that will be used when updating fails, also has an error and the management information is lost. Thus, it becomes impossible not only to continue the updating process but also to read data.
In conventional flash memories, only one bit is stored in each memory cell. If a plurality of bits, such as two bits or four bits, are stored in each memory, the total storage capacity of the flash memory can be increased, and the cost can be reduced. However, in this case, a domino error will affect a greater number of bits, and it will not be able to deal with the error simply by applying an error correction code.